﻿
namespace SortAndDatastruct {
    /// <summary>
    /// 堆排序[不需要额外空间]
    /// 比较排序中，效率最佳的排序算法O(NlgN)
    /// </summary>
    class HeapSort : ISort {
        /// <summary>
        /// 获取左儿子节点
        /// </summary>
        /// <param name="Index">结点索引</param>
        /// <returns>左儿子索引</returns>
        private int Left(ref int Index) {
            return 2 * Index + 1;
        }
        /// <summary>
        /// 调整最小堆
        /// </summary>
        /// <param name="Array">需要转换成堆的数组</param>
        /// <param name="Index">需要检查的索引</param>
        /// <param name="HeapLen">堆的有效长度</param>
        private void Heapify(ref int[] Array, int Index, int HeapLen) {
            if (Array == null || Array.Length < 2 || HeapLen < 2) return;
            int left = Left(ref Index);
            int right = left + 1;
            int largest;
            if (left < HeapLen && Array[left] > Array[Index]) {
                largest = left;
            } else {
                largest = Index;
            }

            if (right < HeapLen && Array[right] > Array[largest]) {
                largest = right;
            }

            if (Index != largest) {
                SortHelper.SWAP(ref Array[Index], ref Array[largest]);
                Heapify(ref Array, largest, HeapLen);
            }
        }
        /// <summary>
        /// 构建最大堆
        /// </summary>
        /// <param name="Array">需要构建的数组</param>
        private void BuildMaxHeap(ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            for (int i = Array.Length / 2; i >= 0; --i) {
                Heapify(ref Array, i, Array.Length);
            }
        }
        /// <summary>
        /// 排序接口
        /// </summary>
        /// <param name="Array">需要排序的数组</param>
        internal override void Sort(ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            BuildMaxHeap(ref Array);
            for (int i = Array.Length - 1; i >= 0; --i) {
                SortHelper.SWAP(ref Array[i], ref Array[0]);
                Heapify(ref Array, 0, i);
            }
        }
    }
}
